/*
    Algorithm exercises
    Copyright (C) 2021 AKCodeDev

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

/*
题目描述
乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。
在每一个移动中，玩家拿出一张牌，得分是用它的数字乘以它左边和右边的数，所以不允许拿第1张和最后1张牌。
最后一次移动后，这里只剩下两张牌，你的目标是使得分的和最小。
例如，如果数是10 1 50 20 5，依次拿1、20、50，总分是10*1*50+50*20*5+10*50*5=8000
而拿50、20、1，总分是1*50*20+1*20*5+10*1*5=1150。
输入
输入文件的第一行包括牌数(3<=n<=100)，第二行包括N个1-100的整数，用空格分开。
输出
输出文件只有一个数字：最小得分。
样例输入
6
10 1 50 50 20 5
样例输出
3650
解析 
区间 dp 模版题
有两种做法，分别是 记忆化搜索 和 区间 dp 。 
记忆化搜索就是把区间分成两份，两份区间递归向下计算，再取所有分法的最小值。不要忘了存储算过的答案。 
而区间 dp 则是将搜索转化成 dp 的形式。 本质完全相同，不过这种方法由于非递归速度更快。 
*/
#include <limits.h>
#include <stdio.h>
#include <string.h>
#define MIN(a, b) ((a)<(b)?(a):(b))
#define N 100
int card[N+5], dp[N+5][N+5], n;
int dfs(int l, int r) {
	if(dp[l][r] || r-l<2)
		return dp[l][r];
	int i, min = INT_MAX;
	for(i = l+1; i < r; i ++)
		min = MIN(min, dfs(l,i)+dfs(i,r)+card[i]*card[l]*card[r]);
	return dp[l][r]=min;
}
int main(){
	int i, j, k;
	scanf("%d", &n);
	for(i = 1; i <= n; i ++)
		scanf("%d", &card[i]);
	/*记忆化搜索*/ 
	printf("%d\n", dfs(1, n));
	/*区间 dp*/ 
	memset(dp, 0, sizeof(dp));
	for(i = 2; i < n; i ++)
		for(j = 1; i + j <= n; j ++) {
			dp[j][i+j] = INT_MAX;
			for(k = j+1; k < i+j; k ++)
				dp[j][i+j] = MIN(dp[j][i+j], dp[j][k]+dp[k][i+j]+card[k]*card[j]*card[i+j]);
		}
	printf("%d", dp[1][n]);
	return 0;
}